package theory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Set;

import compiler.scanner.dfa.DFAState;

public class DFA
{
    public Character[] symbol;              // by symbol index
    public int[][]     stateBySymbolToState;
    // bottom state is always 0 (default transition) (( so 0*any=0 by default ))
    public int[]       acceptingStates;     // state indices of accepting states.
    public int         startingState = 1;

    public DFA(DFAState startState)
    {
        Set<DFAState> allStates = new HashSet<DFAState>();
        Set<Character> symbols = new HashSet<Character>();
        Map<DFAState, Map<Character, DFAState>> transitions = new HashMap<DFAState, Map<Character, DFAState>>();
        Set<DFAState> acceptingStates = new HashSet<DFAState>();

        int stateCounter = 1;
        HashMap<DFAState, Integer> stateToIndex = new HashMap<DFAState, Integer>();
        Queue<DFAState> stateQueue = new LinkedList<DFAState>();
        stateQueue.add(startState);
        while ( !stateQueue.isEmpty())
        {
            DFAState next = stateQueue.poll();
            if (allStates.contains(next))
            {
                continue;
            }
            stateToIndex.put(next, stateCounter ++ );
            stateQueue.addAll(next.transitions.values());
            allStates.add(next);
            symbols.addAll(next.transitions.keySet());
            transitions.put(next, next.transitions);
            if (next.acceptingState)
                acceptingStates.add(next);
        }

        HashMap<Character, Integer> symbolToIndex = new HashMap<Character, Integer>();
        this.symbol = new Character[symbols.size()];
        int i = 0;
        for (char c : symbols)
        {
            this.symbol[i ++ ] = c;
        }
        Arrays.sort(this.symbol);
        i = 0;
        for (char c : this.symbol)
            symbolToIndex.put(c, i ++ );

        this.stateBySymbolToState = new int[allStates.size() + 1/* for bottom state */][symbols.size()];

        for (Entry<DFAState, Map<Character, DFAState>> e : transitions.entrySet())
        {
            int fromState = stateToIndex.get(e.getKey());
            for (Entry<Character, DFAState> arrow : e.getValue().entrySet())
            {
                int symbolIndex = symbolToIndex.get(arrow.getKey());
                int toState = stateToIndex.get(arrow.getValue());

                this.stateBySymbolToState[fromState][symbolIndex] = toState;
            }
        }

        this.acceptingStates = new int[acceptingStates.size()];
        i = 0;
        for (DFAState state : acceptingStates)
            this.acceptingStates[i ++ ] = stateToIndex.get(state);

        Arrays.sort(this.acceptingStates);
    }

    private enum Method
    {
        Union, Intersection
    }

    private DFA intersectOrUnion(DFA other, DFA.Method method)
    {
        // Q = Q1 x Q2
        // Sigma= Sigma1 U Sigma2
        // d((r1,r2),a)=(d(r1,a),d(r2,a))
        // q0 = (q1,q2)
        // Union: final states = F1xQ2 U Q1xF2
        // Intersection: final states = F1 x F2

        Map<Integer, Integer> symbolFirstToIndexFinal = new HashMap<Integer, Integer>();
        Map<Integer, Integer> symbolSecondToIndexFinal = new HashMap<Integer, Integer>();
        Map<Integer, Integer> symbolFinalToIndexSecond = new HashMap<Integer, Integer>();
        Map<Integer, Integer> symbolFinalToIndexFirst = new HashMap<Integer, Integer>();

        Set<Character> allSymbols = new HashSet<Character>();
        for (char s : this.symbol)
            allSymbols.add(s);
        for (char s : other.symbol)
            allSymbols.add(s);

        Character[] symbol = new Character[allSymbols.size()];
        int i = 0;
        for (char s : allSymbols)
        {
            symbol[i ++ ] = s;
        }
        Arrays.sort(symbol);
        i = 0;
        for (char s : symbol)
        {
            symbolFirstToIndexFinal.put(Arrays.binarySearch(this.symbol, s), i);
            symbolSecondToIndexFinal.put(Arrays.binarySearch(other.symbol, s), i);

            symbolFinalToIndexFirst.put(i, Arrays.binarySearch(this.symbol, s));
            symbolFinalToIndexSecond.put(i, Arrays.binarySearch(other.symbol, s));
            i ++ ;
        }

        int startingState = other.startingState + this.stateBySymbolToState.length * this.startingState;

        // start state is always state 1
        // bottom state is always 0 (default transition) (( so 0*any=0 by default ))
        int[][] stateBySymbolToState = new int[this.stateBySymbolToState.length * other.stateBySymbolToState.length][symbol.length];
        for (int q1 = 0; q1 < this.stateBySymbolToState.length; q1 ++ )
        {
            for (int q2 = 0; q2 < other.stateBySymbolToState.length; q2 ++ )
            {
                int combinedState = q2 + this.stateBySymbolToState.length * q1;

                for (int s = 0; s < symbol.length; s ++ )
                {
                    int index1 = symbolFinalToIndexSecond.get(s) < 0 ? 0 : other.stateBySymbolToState[q2][symbolFinalToIndexSecond.get(s)];
                    int index2 = symbolFinalToIndexFirst.get(s) < 0 ? 0 : this.stateBySymbolToState[q1][symbolFinalToIndexFirst.get(s)] * this.stateBySymbolToState.length ;
                    stateBySymbolToState[combinedState][s] = index1 + index2;
                }

            }

        }
        int[] acceptingStates;
        if (method == Method.Intersection)
        {
            acceptingStates = new int[other.acceptingStates.length * this.acceptingStates.length];
            int j = 0;
            for (int a : this.acceptingStates)
                for (int b : this.acceptingStates)
                {
                    int combinedState = b + this.stateBySymbolToState.length * a;
                    acceptingStates[j ++ ] = combinedState;
                }
        }
        else
        // union
        {
            assert method == Method.Union;
            Set<Integer> newAcceptingStates = new HashSet<Integer>();

            for (int a : this.acceptingStates)
                for (int q2 = 0; q2 < other.stateBySymbolToState.length; q2 ++ )
                {
                    int combinedState = q2 + this.stateBySymbolToState.length * a;
                    System.out.println("(" + a + "," + q2 + ") = " + combinedState + " : ACC");
                    newAcceptingStates.add(combinedState);
                }

            for (int q1 = 0; q1 < this.stateBySymbolToState.length; q1 ++ )
                for (int b : other.acceptingStates)
                {
                    int combinedState = b + this.stateBySymbolToState.length * q1;
                    System.out.println("(" + q1 + "," + b + ") = " + combinedState + " : ACC");
                    newAcceptingStates.add(combinedState);
                }

            acceptingStates = new int[newAcceptingStates.size()];
            int j = 0;
            for (int state : newAcceptingStates)
                acceptingStates[j ++ ] = state;
        }

        return new DFA(symbol, stateBySymbolToState, acceptingStates, startingState);
    }

    public DFA(Character[] symbol, int[][] stateBySymbolToState, int[] acceptingStates, int startingState)
    {
        super();
        this.symbol = symbol;
        this.stateBySymbolToState = stateBySymbolToState;
        this.acceptingStates = acceptingStates;
        this.startingState = startingState;
        Arrays.sort(this.acceptingStates);
    }

    public DFA intersect(DFA p)
    {
        return intersectOrUnion(p, Method.Intersection);
    }

    public DFA union(DFA p)
    {
        return intersectOrUnion(p, Method.Union);
    }

    public DFA complement()
    {
        // TODO also invert bottom state ?
        int[] acceptingStates = new int[stateBySymbolToState.length - this.acceptingStates.length];
        int i = 0;
        for (int q1 = 0; q1 < this.stateBySymbolToState.length; q1 ++ )
        {
            if (Arrays.binarySearch(this.acceptingStates, q1) < 0)
                acceptingStates[i ++ ] = q1;
        }
        return new DFA(symbol, stateBySymbolToState, acceptingStates, startingState);
    }

    public boolean isAnyFinalStateReachableFrom(int state)
    {
        ArrayList<Integer> seen = new ArrayList<Integer>();
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(state);
        while ( !queue.isEmpty())
        {
            int s = queue.poll();
            seen.add(s);
            if (isFinalState(s)) { return true; }

            for (int symbol = 0; symbol < this.symbol.length; symbol ++ )
            {
                int next = stateBySymbolToState[s][symbol];
                if (seen.contains(next))
                    continue;
                queue.offer(next);
            }
        }
        return false;
    }

    private boolean isFinalState(int s)
    {
        // TODO Auto-generated method stub
        return Arrays.binarySearch(acceptingStates, s) >= 0;
    }

    public boolean isStateReachableFromStartState(int state)
    {
        ArrayList<Integer> seen = new ArrayList<Integer>();
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(startingState);
        while ( !queue.isEmpty())
        {
            int s = queue.poll();
            seen.add(s);
            if (s == state) { return true; }

            for (int symbol = 0; symbol < this.symbol.length; symbol ++ )
            {
                int next = stateBySymbolToState[s][symbol];
                if (seen.contains(next))
                    continue;
                queue.offer(next);
            }
        }
        return false;
    }
}